1245F - Daniel and Spring Cleaning - CodeForces Solution

#include<bits/stdc++.h>

#pragma GCC optimize(1)

#pragma GCC optimize(2)

#pragma GCC optimize(3,"Ofast","inline")

using namespace std;

typedef long long ll;

ll f[500][2][2];

ll bit1[505],bit2[505];

ll dp(ll def,ll eq1,ll eq2){

    if(!def)return 1;

    if(f[def][eq1][eq2] != -1)return f[def][eq1][eq2];

    ll up1 = eq1?bit1[def]:1;

    ll up2 = eq2?bit2[def]:1;

    ll ans = 0;

    for(int i = 0;i <= up1;i++){

        for(int j = 0;j <= up2;j++){

            if(i+j <= 1)ans += dp(def-1,eq1&&(i==up1),eq2&&(j==up2));

        }

    }

    f[def][eq1][eq2] = ans;

    return ans;

}

ll work(ll x,ll y){

    if(x == -1||y == -1)	return 0;

    memset(f,-1,sizeof(f));

    ll pos = 0;

    for(;x||y;x>>=1,y>>=1){

        bit1[++pos] = x&1;

        bit2[pos] = y&1;

    }

    ll ans = 0;

    ans = dp(pos,1,1);

    return ans;

}

void solve(){

    ll a,b;cin >> a >> b;

    ll ret = work(b,b)-2*work(b,a-1)+work(a-1,a-1);//二维前缀和思想，画图就明白了

    cout << ret << "\n";

}

int main(){

    ios_base::sync_with_stdio(0);

    ll t;cin >> t;

    while(t--)solve();

}